Gödel showed that you can encode any axiomatic system into the natural numbers, and thus provability becomes just a relationship between the mind-bogglingly-large number representing the axioms and the one representing the theorem. I
I’m not sure this is true. I don’t think a Gödel encoding can be done for any axiomatic system. For example, an axiomatic system with uncountably many axioms cannot necessarily be encoded in this way. For most natural systems that have uncountably many axioms you can get around this if the axioms occur in a regular enough fashion, but this isn’t true for all systems. For example, consider ZF but instead of the standard axiom schema of specification, I only include the schema for some very ugly uncountable collection of predicates. This axiomatic system cannot in general be represented by a Gödel numbering. To see this, note that there are at most |P(N)| Godel numbering systems and the cardinality of the collection of single variable predicates in ZF is much larger.
(Disclaimer: I do number theory not model theory or logic so there could be something wrong with this argument.)
My mathematical logic is rusty, but if I’m not mistaken, the relevant criterion is that the set of axioms must be recursively enumerable, i.e. either finite or with a countable number of axioms that are generated using some Turing-equivalent sort of axiom schemas.
A countable set of axioms can be non-recursively-enumerable (i.e. there’s no Turing machine that generates its members, and nothing else, as output). Such sets of axioms clearly cannot be Goedelized, since there are uncountably many of them—whereas for recursively enumerable ones, it’s only necessary to enumerate the Turing machines that generate them.
I think recursively enumerable is sufficient but not necessary. To see an example, consider Peano Arithmetic with added axioms as follows: Pick some lexographic ordering of all well-formed formula in PA, and denote this system by P_0. Define Pn for n>1 by running through your list of statements until you come to one that isn’t provable or disprovable in P(n-1). When you do, throw it in as true with the axioms of P_(n-1) to get P_n. Consider then the system P_infinity = the union of all the P_i. This system has only finitely many axioms, is Godel numerable by most definitions of that term but is not recursively enumerable (since if it were we’d have a decision procedure for PA.)
Yes, you’re right, of course. In my above comment, I failed to consider that not only Turing machines can be Goedelized, but also various infinite-step procedures that produce non-computable results, such as the one you outlined above.
(Also, I assume you meant “countably,” not “finitely” in the last sentence.)
Yes, I do think that only countable things exist. I believe that the TOE and the universe are natural numbers. (Well, of course, there is a countable infinity of isomorphic universes, but in terms of existence, I count those as just one.)
The actual contents of the universe are thus countable (though eternally looping in a complex temperospatial topology).
I thought that saying “natural” number was enough to make these points. Sorry.
I don’t think a Gödel encoding can be done for any axiomatic system. For example, an axiomatic system with uncountably many axioms cannot necessarily be encoded in this way.
My mathematical logic is rusty, but if I’m not mistaken, the same holds for a set of axioms that’s countable, but non-computable.
I’m not sure this is true. I don’t think a Gödel encoding can be done for any axiomatic system. For example, an axiomatic system with uncountably many axioms cannot necessarily be encoded in this way. For most natural systems that have uncountably many axioms you can get around this if the axioms occur in a regular enough fashion, but this isn’t true for all systems. For example, consider ZF but instead of the standard axiom schema of specification, I only include the schema for some very ugly uncountable collection of predicates. This axiomatic system cannot in general be represented by a Gödel numbering. To see this, note that there are at most |P(N)| Godel numbering systems and the cardinality of the collection of single variable predicates in ZF is much larger.
(Disclaimer: I do number theory not model theory or logic so there could be something wrong with this argument.)
Eh, that’s a nitpick. Author could have just said ‘countable’ or even ‘finite’.
My mathematical logic is rusty, but if I’m not mistaken, the relevant criterion is that the set of axioms must be recursively enumerable, i.e. either finite or with a countable number of axioms that are generated using some Turing-equivalent sort of axiom schemas.
A countable set of axioms can be non-recursively-enumerable (i.e. there’s no Turing machine that generates its members, and nothing else, as output). Such sets of axioms clearly cannot be Goedelized, since there are uncountably many of them—whereas for recursively enumerable ones, it’s only necessary to enumerate the Turing machines that generate them.
I think recursively enumerable is sufficient but not necessary. To see an example, consider Peano Arithmetic with added axioms as follows: Pick some lexographic ordering of all well-formed formula in PA, and denote this system by P_0. Define Pn for n>1 by running through your list of statements until you come to one that isn’t provable or disprovable in P(n-1). When you do, throw it in as true with the axioms of P_(n-1) to get P_n. Consider then the system P_infinity = the union of all the P_i. This system has only finitely many axioms, is Godel numerable by most definitions of that term but is not recursively enumerable (since if it were we’d have a decision procedure for PA.)
Yes, you’re right, of course. In my above comment, I failed to consider that not only Turing machines can be Goedelized, but also various infinite-step procedures that produce non-computable results, such as the one you outlined above.
(Also, I assume you meant “countably,” not “finitely” in the last sentence.)
Yes, I do think that only countable things exist. I believe that the TOE and the universe are natural numbers. (Well, of course, there is a countable infinity of isomorphic universes, but in terms of existence, I count those as just one.)
The actual contents of the universe are thus countable (though eternally looping in a complex temperospatial topology).
I thought that saying “natural” number was enough to make these points. Sorry.
JoshuaZ:
My mathematical logic is rusty, but if I’m not mistaken, the same holds for a set of axioms that’s countable, but non-computable.